package com.demo.java.OD251_300.OD260;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【按路径替换二叉树】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146058497
 */
public class OdMain {
    // 定义二叉树节点类
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        // 解析输入
        String str1 = in.nextLine();
        int[] num1 = parseStringArrayToIntArray(str1.substring(1, str1.length() - 1).split(","));

        String str2 = in.nextLine();
        int[] num2 = parseStringArrayToIntArray(str2.substring(1, str2.length()).split("/"));

        String str3 = in.nextLine();
        int[] num3 = parseStringArrayToIntArray(str3.substring(1, str3.length() - 1).split(","));

        // 构建树1和树2
        TreeNode treeNode1 = build(num1, 0);
        TreeNode treeNode2 = build(num3, 0);

        // 替换操作
        if (num2.length > 1) {
            replace(treeNode1, treeNode2, num2, 1);
        } else {
            treeNode1 = treeNode2;
        }

        // 层次遍历输出结果
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(treeNode1);

        StringBuilder ans = new StringBuilder("[");
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            ans.append(node.val).append(",");
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        ans.setLength(ans.length() - 1); // 删除最后的逗号
        ans.append("]");
        System.out.println(ans.toString());
    }

    // 根据数组构建二叉树
    public static TreeNode build(int[] nums, int index) {
        TreeNode newNode = null;
        if (index < nums.length && nums[index] != 0) {
            newNode = new TreeNode(nums[index]);
            newNode.left = build(nums, 2 * index + 1);
            newNode.right = build(nums, 2 * index + 2);
        }
        return newNode;
    }

    // 路径替换操作
    public static void replace(TreeNode root1, TreeNode root2, int[] path, int i) {
        if (i == path.length - 1) {
            if (root1.left != null && root1.left.val == path[i]) {
                root1.left = root2;
                return;
            } else if (root1.right != null && root1.right.val == path[i]) {
                root1.right = root2;
                return;
            }
        }

        if (root1.left != null && root1.left.val == path[i]) {
            replace(root1.left, root2, path, i + 1);
        } else if (root1.right != null && root1.right.val == path[i]) {
            replace(root1.right, root2, path, i + 1);
        }
    }

    // 字符串转整数数组
    public static int[] parseStringArrayToIntArray(String[] s) {
        return Arrays.stream(s).mapToInt(Integer::parseInt).toArray();
    }
}